﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Alice.Sort
{
	public class QuickSort
	{

        // 实现快速排序[start, end]
        public static void Sort(ref int[] arr, int start, int end)
        {
            // 循环结束条件
            if (start >= end)
                return;

            // 开始递归
            int i = Partition(ref arr, start, end);
            Sort(ref arr, start, (i - 1));
            Sort(ref arr, (i + 1), end);
        }   

        // 将[start,end]数组分割
        public static int Partition(ref int[] arr, int start, int end)
        {
            // 选择主元，这里总是选择最后一个元素作为主元，或者这里
            // 通过随机数随机选择主元
            int pivot = arr[end];
            int i = start - 1;  // 游标i之前(<=i)应该全是小于pivot的元素
            int tmp;

            for (int j = start; j <= end - 1; ++j )
            {
                // 升序排列
                if (arr[j] < pivot)
                {
                    ++i;
                    // 交换两个元素arr[i]和arr[j]
                    tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
                }
            }
            // 将pivot(arr[end])的元素放置在(i + 1)的位置
            tmp = arr[end];
            arr[end] = arr[i + 1];
            arr[i + 1] = tmp;

            return (i + 1);
        }


	}
}
